{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## _*Using Qiskit Aqua for set packing problems*_\n",
    "\n",
    "Given a collection $S$ of subsets of a set $X$, the set packing problem tries to find the subsets that are pairwise disjoint (in other words, no two of them share an element). The goal is to maximize the number of such subsets.\n",
    "\n",
    "We will go through two examples to show:\n",
    "1. How to run the optimization\n",
    "2. How how to run the optimization with the VQE."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### The problem and the brute-force method.\n",
    "\n",
    "The problem is as follows. First, let us print the list of subsets."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[4, 5], [4], [5]]\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "import json\n",
    "\n",
    "from qiskit import BasicAer\n",
    "from qiskit.optimization.applications.ising import set_packing\n",
    "from qiskit.aqua.algorithms import NumPyMinimumEigensolver\n",
    "from qiskit.optimization.applications.ising.common import sample_most_likely\n",
    "\n",
    "\n",
    "input_file = 'sample.setpacking'\n",
    "with open(input_file) as f:\n",
    "    list_of_subsets = json.load(f)\n",
    "    print(list_of_subsets)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The brute-force method is as follows. Basically, we exhaustively try all the binary assignments. In each binary assignment, the entry of a subset is either 0 (meaning the subset is not taken) or 1 (meaning the subset is taken). We print the binary assignment that satisfies the definition of the set packing. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Size of set packing 2\n"
     ]
    }
   ],
   "source": [
    "def brute_force():\n",
    "    # brute-force way: try every possible assignment!\n",
    "    def bitfield(n, L):\n",
    "        result = np.binary_repr(n, L)\n",
    "        return [int(digit) for digit in result]  # [2:] to chop off the \"0b\" part\n",
    "\n",
    "    L = len(list_of_subsets)\n",
    "    max = 2**L\n",
    "    max_v = -np.inf\n",
    "    for i in range(max):\n",
    "        cur = bitfield(i, L)\n",
    "        cur_v = set_packing.check_disjoint(cur, list_of_subsets)\n",
    "        if cur_v:\n",
    "            if np.count_nonzero(cur) > max_v:\n",
    "                max_v = np.count_nonzero(cur)\n",
    "    return max_v\n",
    "\n",
    "size = brute_force()\n",
    "print(\"Size of set packing\", size)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "qubit_op, offset = set_packing.get_operator(list_of_subsets)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Part I: Run the optimization \n",
    "\n",
    "Here we directly construct the algorithm and then run() it to get the result."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Size of set packing 2\n"
     ]
    }
   ],
   "source": [
    "algo = NumPyMinimumEigensolver(qubit_op)\n",
    "result = algo.run()\n",
    "\n",
    "x = sample_most_likely(result.eigenstate)\n",
    "ising_sol = set_packing.get_solution(x)\n",
    "np.testing.assert_array_equal(ising_sol, [0, 1, 1])\n",
    "oracle = brute_force()\n",
    "print(\"Size of set packing\", np.count_nonzero(ising_sol))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Part II: Run the optimization with the VQE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can create the objects directly ourselves too and run VQE for the result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Size of set packing 2\n"
     ]
    }
   ],
   "source": [
    "from qiskit.aqua import aqua_globals\n",
    "from qiskit.aqua.algorithms import VQE\n",
    "from qiskit.aqua.components.optimizers import COBYLA\n",
    "from qiskit.circuit.library import TwoLocal\n",
    "\n",
    "aqua_globals.random_seed = 100\n",
    "\n",
    "optimizer = COBYLA()\n",
    "var_form = TwoLocal(qubit_op.num_qubits, 'ry', 'cz', reps=5, entanglement='linear')\n",
    "vqe = VQE(qubit_op, var_form, optimizer)\n",
    "\n",
    "backend = BasicAer.get_backend('statevector_simulator')\n",
    "result = vqe.run(backend)\n",
    "\n",
    "x = sample_most_likely(result.eigenstate)\n",
    "ising_sol = set_packing.get_solution(x)\n",
    "print(\"Size of set packing\", np.count_nonzero(ising_sol))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
